package erfenchazhao;

public class Text {
    //题目链接:https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/
    public int takeAttendance(int[] records) {
        //这道题有很多种解法  但是最优解法是二分查找
        //这道题只要找出二段线 就十分简单
        //可以写出数组元素对应的下标    就会发现 可以分成两部分  一部分是
        //下标和元素是相等的   另一部分是下标是比元素小1 的   我们要找的值就是另一部分的值的最左端的下标

        int left = 0,right = records.length - 1;
        while(left < right ) {
            int mid = left + (right - left) /2;
            if(records[mid] == mid) {
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        //这里返回的时候要注意一种特殊情况 就是刚好缺失 的是最后一个元素  二分查找是找不到的
        if(records[left] == left) {
            return left + 1;
        }
        return left;
    }

    //另一种解法
    public int takeAttendance1(int[] records) {
        //这道题也可以根据等差数列的和来做 求和  遍历数组 减掉有的元素 剩下的就是没有的元素
        int n = records.length;
        //定义一个变量记录一下和
        int sum = n *(n +1) / 2;
        for(int a : records) {
            sum = sum - a;
        }
        return sum;
    }



    //已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
    //若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
    //若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
    //注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
    //
    //给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

    public int findMin(int[] nums) {
        //也是用二分查找   有二段性  一种是大于nums[n - 1] 一种是小于等于numss[n- 1]
        int n = nums.length;
        int left = 0,right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] > nums[n -1]) {
                left = mid + 1;
            } else{
                right = mid;
            }
        }
        return nums[left];
    }

    //峰值元素是指其值严格大于左右相邻值的元素。
    //给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
    public int findPeakElement(int[] nums) {
        //利用二分查找  有二段性
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) /2;
            if(nums[mid] > nums[mid + 1]) {
                right = mid;
            }else{
                left = mid +1;
            }
        }
        return left;
    }
    public static void main(String[] args) {

    }
}
